package algorithm.leetcode.I1to100;

import algorithm.leetcode.ListNode;

public class Q25 {

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode fakeHead = new ListNode(-1);
        fakeHead.next = head;
        ListNode temp = fakeHead;

        while (temp != null) {
            temp = reverseHelper(temp, k);
        }
        return fakeHead.next;

    }


    private ListNode reverseHelper(ListNode node, int k) {
        int count = 0;
        ListNode curr = node;
        ListNode begin = node.next;
        while (count < k && curr != null) {
            curr = curr.next;
            count ++;
        }

        // 长度不小于k,执行反转
        if (count == k && curr != null) {
            ListNode prev = null;
            curr = node.next;
            ListNode post = null;
            node.next = null;

            while (count > 0) {
                post = curr.next;
                curr.next = prev;
                prev = curr;
                curr = post;
                count--;
            }
            // 操作反转链表的前后
            begin.next = curr;
            node.next = prev;
            return begin;
        }
        // 否则,返回null表示当前node后续节点个数已不足k个
        else {
            return null;
        }
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        Q25 q25 = new Q25();
        System.out.println(q25.reverseKGroup(node1, 2));
    }
}
